class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]

    def find(self, x):
        if x != self.root[x]:
            # 将该节点的根节点递归改为鼻祖根节点
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            self.root[rootx] = rooty

    def get_root(self):
        return self.root


def findCircleNum(isConnected):
    if not isConnected:
        return 0
    n = len(isConnected)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(n):
            if isConnected[i][j] == 1 and i != j:
                uf.union(i, j)
    # 找一遍
    for i in range(n):
        uf.find(i)
    root = uf.get_root()
    return len(set(root))


isConnected = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
print(findCircleNum(isConnected))  # 3
